#include "dfa.h"
#include <sstream>

namespace regex
{

bool DfaMatcher::match(const Dfa &dfa, const std::string &str, MatchResult &mr)
{
    uint curr = dfa.get_start_state();
    uint next = 0;
    bool ever_matched = dfa.is_accept(curr);

    for (size_t i = 0; i < str.size(); ++i)
    {
        Input input(str, i);
        if (!dfa.get_next_state(curr, input, next))
        {
            break;
        }

        if (dfa.is_accept(next))
        {
            mr.m_end = i + 1;
            ever_matched = true;
            break;
        }     
    }
    
    return ever_matched;
}

std::map<std::string, uint> s_states_map;
uint DfaBuilder::s_dfa_curr = 0;

uint DfaBuilder::get_next_dfa_state(const std::vector<uint> &states)
{
    std::ostringstream oss;
    for (size_t i = 0; i < states.size(); ++i)
    {
        oss << states[i] << ' ';
    }
    std::string str = oss.str();

    std::map<std::string, uint>::iterator find = s_states_map.find(str);
    if (find != s_states_map.end())
    {
        return find->second;
    }
    
    uint value = s_dfa_curr++;
    s_states_map[str] = value;
    return value;
}

bool DfaBuilder::build(const Nfa &nfa, Dfa &dfa)
{
    std::vector<uint> nfa_curr;
    std::vector<uint> nfa_next;
    std::vector<Transition> nfa_trans;

    std::string empty_str;
    Input epsilon(empty_str, 0);

    nfa_curr.push_back(nfa.get_start_state());
    nfa.get_next_states(nfa.get_start_state(), epsilon, nfa_curr);

    unique(nfa_curr);
    uint dfa_curr = get_next_dfa_state(nfa_curr);

    std::string dfa_trigger;

    while (!nfa_curr.empty())
    {
        for (size_t i = 0; i < nfa_curr.size(); ++i)
        {
            uint curr = nfa_curr[i];

            nfa_trans.clear();
            nfa.get_transitions(curr, nfa_trans);

            for (size_t j = 0; j < nfa_trans.size(); ++j)
            {
                Transition nfa_tran = nfa_trans[j];
                dfa_trigger += nfa_tran.m_trigger.m_string;
                nfa_next.push_back(nfa_tran.m_next);
            }
        }
        
        uint nfa_size = nfa_next.size();
        for (size_t i = 0; i < nfa_size; ++i)
        {
            nfa.get_next_states(nfa_next[i], epsilon, nfa_next);
        }
        
        unique(nfa_next);    
        uint dfa_next = get_next_dfa_state(nfa_next);
    
        unique(dfa_trigger);
        dfa.add_transition(dfa_curr, dfa_next, dfa_trigger);

        if (nfa.remove_accept(nfa_next))
        {
            dfa.set_accept(dfa_next);
        }
    
        std::swap(nfa_curr, nfa_next);
        nfa_next.clear();
        dfa_curr = dfa_next;
    }
    
    return true;
}

}